package com.kobe.algorithm.leetcode.case146;


import java.util.HashMap;
import java.util.Map;

/**
 * @author ：caopengfei
 * @date ：2021/2/23
 */
public class LRUCache {

     LinkNode head;
     LinkNode tail;
     int capacity = 0;
     int size = 0;
     Map<Integer,LinkNode> cache = new HashMap<>();

     class LinkNode{
         LinkNode prev;
         LinkNode next;
         int key;
         int value;
         public LinkNode() {}

         public LinkNode(int key, int value) {
             this.key = key;
             this.value = value;
         }
     }

    public LRUCache(int capacity) {
         this.capacity = capacity;
         int size = 0;
         head = new LinkNode();
         tail = new LinkNode();
         head.next = tail;
         tail.prev = head;
    }

    public void put(int key,int value){
        LinkNode node = cache.get(key);
        if(node == null){
            LinkNode newNode = new LinkNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            ++size;
            if(size > capacity){
                LinkNode tailNode = removeTail();
                cache.remove(tailNode.key);
                --size;
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }
    public int get(int key){
         LinkNode node = cache.get(key);
         if(node == null){
             return -1;
         }else{
             moveToHead(node);
             return node.value;
         }
    }

    private void addToHead(LinkNode node){
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(LinkNode node){
         node.prev.next = node.next;
         node.next.prev = node.prev;
    }

    private void moveToHead(LinkNode node){
        removeNode(node);
        addToHead(node);
    }

    private LinkNode removeTail(){
        LinkNode tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }


    public static void main(String[] args) {

        LRUCache cache = new LRUCache(10);

        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(2, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(2));    // 返回 1
        lRUCache.put(1, 1); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache.put(4, 1); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
    }
}
